package com.lisp.algorithm.test.sort;

import java.util.Random;

public class QuickSelect {

	public static void main(String[] args) {
		int a[] = {0, 8, 2, 10, 1, 2, 5, 3, 7, 8, 5};
		for(int i=0; i<10; i++) {			
			System.out.println(quickSelect(a, 0, a.length-1, 4));
		}
	}
	
	private static int quickSelect(int a[], int start, int end, int ith) {
		if(start < end) {
			int partitionIndex = partition(a, start, end);
			if(partitionIndex == ith) {
				return a[partitionIndex];
			} else if(partitionIndex < ith) {
				return quickSelect(a, partitionIndex+1, end, ith);
			} else {
				return quickSelect(a, start, partitionIndex-1, ith);
			}
		} else {
			return a[start];
		}
	}
	
	private static int partition(int a[], int start, int end) {
		
		int pivotIndex = start + new Random().nextInt(end-start);
		int pivotValue = a[pivotIndex];

		swap(a, pivotIndex, start);
		
		int i=start, j=end+1;
		while(true) {
			do {
				i++;
			} while(i <= end && a[i] < pivotValue);
			
			do {
				j--;
			} while(j > start && a[j] > pivotValue);
			
			if(i >= j) {
				swap(a, start, j);
				return j;
			} else {
				swap(a, i, j);
			}
		}
	}
	
	private static void swap(int a[], int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
}
